package com.cat.binaryTree;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/smallest-string-starting-from-leaf/description/
 * @create 2025/9/10 18:50
 * @since JDK17
 */

public class Solution14 {
    String ans = null;

    void dfs(TreeNode root, StringBuilder cur) {
        cur.append(((char) (root.val + 'a')));
        if (root.left == null && root.right == null) {
            StringBuilder temp = new StringBuilder();
            for (int i = cur.length() - 1; i >= 0; i--) {
                temp.append(cur.charAt(i));
            }
            if (ans == null || ans.compareTo(temp.toString()) > 0) {
                ans = temp.toString();
            }
        } else {
            if (root.left != null) {
                dfs(root.left, cur);
            }
            if (root.right != null) {
                dfs(root.right, cur);
            }
        }

        cur.setLength(cur.length() - 1);
    }

    public String smallestFromLeaf(TreeNode root) {
        dfs(root, new StringBuilder());
        return ans;
    }
}
